package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         61,
		Discription: "旋转链表",
		Level:       2,
		Labels: map[string]int{
			"链表": 1,
		},
	})
}

func RotateRight(head *ds.ListNode, k int) *ds.ListNode {
	//注意3种直接返回的情况
	if head == nil || head.Next == nil || k == 0 {
		return head
	}

	length := 1
	temp := head
	//先遍历一遍，把链表首尾相连
	for temp.Next != nil {
		length++
		temp = temp.Next
	}
	temp.Next = head

	//得到有效的翻转位置
	k %= length
	newTail := head
	//根据k找到旋转后链表的最后一个节点，把最后一个节点的next作为新的节点，然后把next置为nil
	for i := 1; i < length-k; i++ {
		newTail = newTail.Next
	}
	newHead := newTail.Next
	newTail.Next = nil
	return newHead
}
